#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=120 lang=cpp
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
class Solution {
public:
    // dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + t[i][j]
    // 
    int minimumTotal(vector<vector<int>>& triangle) {
        int rows = triangle.size(), res = INT_MAX;
        vector<int> dp(rows, 0); 
        for (int i = 0; i < rows; i++) {
            for (int j = i; j >= 0; j--) {
                if (j == i && i != 0) dp[j] = dp[j - 1] + triangle[i][j];
                else if (j > 0) dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
                else dp[j] = dp[j] + triangle[i][j];
                if (i == rows - 1) res = min(res, dp[j]);
            }
        }
        return res;
    }
};
// @lc code=end

